1. Field of the Invention
This invention relates to an electronic circuit. More particularly, although not exclusively, it relates to an electronic circuit for determination of distances between reference and data points.
2. Discussion of Prior Art
Electronic circuits for determining Euclidean distances are known in the prior art. Such a circuit incorporates a stored quantity corresponding to a reference point and accepts as input a signal representing a data point. It produces a measure of the distance between the input signal and the stored quantity. Such circuits are useful in applications in which calculations of Euclidean distance would consume a substantial amount of computing capacity. In visual and speech recognition, together with other forms of pattern recognition, it is necessary to determine Euclidean distance between large numbers of input data points and each point in a large database of reference points.
U.S. Pat. No. 3,864,558 discloses a pair of field effect transistors (FETs) with programmable memories arranged to determine the square of the distance between two points represented by voltages. The FET memories are programmed by setting the threshold voltage. When the transistors are operated in saturation, the output current is dependent on the square of the difference between this programmed voltage and an applied gate voltage and hence is representative of the distance required. A p-channel and an n-channel FET are connected source to drain in antiparallel. The two gates are connected together such that only one FET conducts under an applied gate bias, the particular FET producing the distance representation being dependent on whether the applied gate voltage is greater or less than the stored threshold voltage. In this way an analogue for the square of the difference between a first magnitude and a second magnitude is produced regardless of the polarity of this difference. Using dissimilar-type FETs however makes it difficult to match device characteristics. Differing carrier mobilities and other physical characteristics mean that extreme difficulty is met in making allowance for the effects of device mismatch.
In "A Neural Network Capable of Forming Associations by Example", Neural Networks Vol. 2 pages 395-403, 1989, Hartstein and Koch disclose a similar arrangement of FETs. A two-transistor circuit is used in a neural network to represent the difference between a voltage input and a stored or learned value. Two metal oxide semiconductor field effect transistors (MOSFETs), a p-channel and an n-channel MOSFET are this time connected in parallel in a symmetric arrangement in order to obtain a symmetric output function for the neural network. Hartstein and Koch are not however concerned with Euclidean distance determination, but instead output function symmetry. This symmetry requires close matching of the characteristics of the p-channel and n-channel devices and if it is not achieved, the output of the circuit is not suitable for Euclidean distance determination.
In "Programmable Analogue VLSI for Radial Basis Function Networks", Electronics Letters 29(18), pages 1663-1665, September 1993, Churcher et al. describe a transconductance amplifier which produces an output current proportional to the square of the difference (distance) between an input voltage and a stored voltage maintained by a capacitor. The amplifier produces an approximation to the square of the Euclidean distance between the input and stored voltages. It is not suitable for applications such as pattern recognition requiring a large number of distance measuring circuits. It incorporates a number of transistors, two of which are considerably wider than the rest, which gives rise to difficulty as regards formation of large arrays. The transistors also suffer from high power consumption when operating in their saturation region.
A similar disadvantage is apparent in the circuit described in "CMOS Selfbiased Euclidean Distance Computing Circuit with High Dynamic Range", Electronics Letters 28 (4) page 352, 1992. O. Landolt, E. Vittoz and P. Heim describe a device which outputs a representation of the function ##EQU1## for the n-dimensional vector of bi-directional currents I.sub.1, . . . I.sub.n. However, to calculate Euclidean distance, these currents cannot be representative of vector components in themselves but of the difference between vector components. Such currents can be generated using a simple switched-current memory cell, but this will require a minimum of four extra transistors per dimension. Thus the complete circuit containing both the square-law distance calculation and the current memories is not sufficiently compact for practicable incorporation into large arrays.
A two-transistor cell has been designed by Castro and Park (U.S. Pat. No. 4,999,525). It employs two floating gate transistors to implement an exclusive-or operation between two digital patterns. Cells are cascaded together to calculate a Hamming distance between an input vector and a stored reference vector. The cell requires a separate high-gain inverter to complement the input vector, restricting the cell to digital operation.
In "An Analog VLSI Chip for Radial Basis Functions", Advances in Neural Information Processing Systems 5, Morgan Kaufmann 1933, Anderson et al. disclose a distance determination chip employing an inverter with an adjustable threshold. The threshold is set using a floating gate device such as that described by S. M. Sze in "Physics of Semiconductor Devices", Wiley 2nd Edition 1981, page 496. This device is programmed using a combination of non-avalanche injection and tunnelling.
The Anderson et al. circuit has a major disadvantage that its output does not correspond to a true Euclidean distance or square of a Euclidean distance. Instead, the output current approximates to a quadratic function only in the region of a peak current value. The approximation is only valid over a short range of input voltages, less than 0.35V in the implementation of Anderson et al.
A low-power difference calculating neural network developed by M. A. Holler, S. M. Tam and A. H. Kramer is described in UK Patent Application 2 267 172. This network calculates the absolute "City Block Distance" between an input voltage and a stored reference point, referred to as a weight. The weight is stored by means of a floating gate charge which determines the threshold voltage of the device. An applied input (data) voltage causes charges to develop within the channel regions of selected MOSFETs, the magnitude of this charge being proportional to the difference between the applied data voltage and the threshold voltage.
The MOSFETs of the same column are then discharged and the associated charge packets of a column of MOSFETs are summed. This summed charge thus represents the City Block distance for that column.
The City Block calculation does not have as many or as useful applications as the Euclidean distance calculation. City Block, also known as Manhattan, distances are sensitive to a change of axes and so assumptions have to be made regarding the nature of the data in order that appropriate axes are selected. Euclidean distance is far more useful in practical applications because its inherent symmetry renders it independent of axes orientation. It thus offers a more robust and portable technique for distance calculation. Further disadvantages arise from operating in the charge domain in preference to the current domain. The accuracy with which charge is stored on floating gate devices is generally an indeterminable quantity; the reference level may therefore carry an inherent uncertainty. Moreover, even identically produced MOSFETs exhibit inter-device variations leading to differing threshold voltages.
Each of the foregoing prior art techniques suffers from at least one of the following disadvantages: unadapted to Euclidean distance calculation, large chip area requirements, high power consumption and restriction to a short range of input voltages or to digital implementation only. There is a perceived need for a circuit which admits of compact construction, is operative over a useful range of input voltages, calculates the more useful Euclidean distance and is suitable for analogue implementation. There is also a trend towards developing lower-power devices suitable for distance calculations in portable systems.